/*
day349 
2020.8.11 
*/
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

class Solution {
public:
    vector<int> subSort(vector<int>& array) {
		int m=-1,n=-1;
		if(array.empty())
		{
			return {m,n};
		 } 
		
		int *max_l=new int[array.size()];
		max_l[0]=array[0];
		for(int i=1;i<array.size();++i)
		{
			max_l[i]=max(max_l[i-1],array[i]);
		}
		
		int *min_r=new int[array.size()];
		min_r[array.size()-1]=array[array.size()-1];
		for(int i=array.size()-2;i>=0;--i)
		{
			min_r[i]=min(min_r[i+1],array[i]);
		}
		

		for(int i=1;i<array.size();++i)
		{
			if(min_r[i]<array[i-1])
			{
				m=i-1;
				break;
			}
		}
		
		for(int i=array.size()-1;i>0;--i)
		{
			if(max_l[i-1]>array[i])
			{
				n=i;
				break;
			}
		}
		
		return {m,n};
    }
};


class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        if (!array.size()) return {-1, -1};
        vector<bool> dp(array.size(), true);
        int maxval = array[0];
        for (int i = 0; i < array.size(); ++i) {
            if (array[i] < maxval) {
                dp[i] = false;
            } else {
                maxval = array[i];
            }
        }
        int minval = array[array.size()-1];
        int rmax = -1;
        int rmin = array.size();
        for (int i = array.size()-1; i >= 0; --i) {
            if (array[i] > minval) {
                dp[i] = false;
            } else {
                minval = array[i];
            }
            if (!dp[i]) {
                rmax = max(rmax, i);
                rmin = min(rmin, i);
            }
        }
        if (rmax == -1) return {-1, -1};
        return {rmin, rmax};
    }
};


int main()
{
	return 0;
}
